
/*

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/multiply-strings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

class Solution {
public:
    string multiply(string num1, string num2) {
        int n1=num1.size();
        int n2=num2.size();
        //最多n1 + n2 位
        string res(n1+n2, '0');
        for(int i = n2 - 1; i >= 0; i--){
            for(int j = n1 - 1; j >= 0; j--){
                int temp = (res[i + j + 1] - '0') + (num1[j] - '0') * (num2[i] - '0');
                res[i+j+1] = temp % 10 + '0';//当前位
                res[i+j] += temp / 10 ; //前一位加上进位，res[i+j]已经初始化为'0'，加上int类型自动转化为char，所以此处不加'0'
            }
        }
        
//去除首位'0'
        for(int i = 0; i < n1+n2; i++){
            if(res[i] != '0')
                return res.substr(i);
        }
        return "0"; 
       
        
    }
};